﻿# -*- coding:utf-8 -*-
import enum
import os
# 测试开关，打开时会打印每一次指令执行后内存的当前状态
Debug = False

# 内存模拟部分
PoolSize = 256 * 1024
PoolSize = 1000
memory = [] # 模拟内存
text = 0 # 代码段的起始位置
data = 0 # 数据段的起始位置
heap = 0 # 堆的起始位置
stack = 0 # 栈的栈顶位置
bp = 0 # 基址
sp = 0 # 
pc = 0 # 程序计数器
ax = 0 # 寄存器（本虚拟机只有一个寄存器）

# 源码
src = ""
s_idx = 0

# 定义虚拟机指出的指令集系统，完全按照c4的指令集系统实现
Inst = enum.Enum("Inst", 
(
    "LEA", "IMM", "JMP", "CALL", "JZ", "JNZ", "ENT", "ADJ", "LEV", "LI", "LC", "SI", "SC", "PUSH",
    "OR", "XOR", "AND", "EQ", "NE", "LT", "GT", "LE", "GE", "SHL", "SHR", "ADD", "SUB", "MUL", "DIV", "MOD",
    "OPEN", "READ", "CLOS", "PRTF", "MALC", "FREE", "MSET", "MCMP", "EXIT",
))

# 关键字
Token = enum.Enum("Token",
(
    "NUM", "FUN", "SYS", "GLO", "LOC", "ID",
    "CHAR", "ELSE", "ENUM", "IF", "INT", "RETURN", "SIZEOF", "WHILE",
    "ASSIGN", "COND", "LOR", "LAN", "OR", "XOR", "AND", "EQ", "NE", "LT", "GT", "LE", "GE", "SHL", "SHR", "ADD", "SUB", "MUL", "DIV", "MOD", "INC", "DEC", "BRAK"
), start = 128)
symbol = []
token = 0
token_val = 0
current_id = {}
main_id = 0
line = 0

# 支持的数据类型
Type = enum.Enum("Type", ("CHAR", "INT", "PTR"))

# 词法分析
def next():
    global s_idx, symbol, token, token_val, current_id, line
    lpos = 0
    lhash = 0
    while s_idx < len(src):
        token = src[s_idx]
        s_idx += 1
        if token == "\n":
            line += 1
        elif (ord(token) >= ord("a") and ord(token) <= ord("z")) or\
            (ord(token) >= ord("A") and ord(token) <= ord("Z")) or\
            token == "_":
            # 字母数字下划线变量名的开头
            lpos = s_idx - 1
            lhash = ord(token)
            token = src[s_idx]
            while (ord(token) >= ord("a") and ord(token) <= ord("z")) or\
                (ord(token) >= ord("A") and ord(token) <= ord("Z")) or\
                (ord(token) >= ord("0") and ord(token) <= ord("9")) or\
                token == "_":
                lhash = lhash * 147 + ord(token)
                s_idx += 1
                if s_idx >= len(src):
                    break
                token = src[s_idx]
            name = src[lpos : s_idx]
            # 已经存在的token
            for x in symbol:
                if x["Hash"] != lhash or x["Name"] != name:
                    continue
                current_id = x
                token = (x["Token"])
                return
            # 发现的新token
            t = {}
            t["Token"] = Token.ID
            t["Hash"] = lhash
            t["Name"] = name
            t["Type"] = 0
            t["Class"] = 0
            t["Value"] = 0
            t["GType"] = 0
            t["GClass"] = 0
            t["GValue"] = 0
            symbol.append(t)
            current_id = t
            token = Token.ID
            return
        elif ord(token) >= ord("0") and ord(token) <= ord("9"):
            token_val = ord(token) - ord("0")
            token = src[s_idx]
            if token_val > 0:
                # 十进制数字
                while ord(token) >= ord("0") and ord(token) <= ord("9"):
                    token_val = token_val * 10 + ord(token) - ord("0")
                    s_idx += 1
                    if s_idx >= len(src):
                        break
                    token = src[s_idx]
            elif token == "X" or token == "x":
                # 十六进制数字以0x开头
                s_idx += 1
                token = src[s_idx]
                while (ord(token) >= ord("0") and ord(token) <= ord("9")) or\
                    (ord(token) >= ord("a") and ord(token) <= ord("f")) or \
                    (ord(token) >= ord("A") and ord(token) <= ord("F")):
                    token_val = token_val * 16 + (ord(token) & 0xF) + (9 if ord(token) >= ord("A") else 0)
                    s_idx += 1
                    if s_idx >= len(src):
                        break
                    token = src[s_idx]
            else:
                while ord(token) >= ord("0") and ord(token) <= ord("7"):
                    token_val = token_val * 8 + ord(token) - ord("0")
                    s_idx += 1
                    if s_idx >= len(src):
                        break
                    token = src[s_idx]
            token = Token.NUM
            return
        elif token == '"' or token == "'":
            # 字符串
            lpos = s_idx
            while s_idx < len(src) and src[s_idx] != token:
                s_idx += 1
            if token == "'":
                token_val = ord(src[lpos])
                token = Token.NUM
            else:
                token_val = didx
                DATA(src[lpos: s_idx])
            s_idx += 1
            return
        elif token == "/":
            if s_idx < len(src) and src[s_idx] == "/":
                # 注释会被完全跳过，因而不会返回
                while s_idx < len(src) and src[s_idx] != "\n":
                    s_idx += 1
                s_idx += 1
            else:
                token = Token.DIV
                return
        elif token == "=":
            if s_idx < len(src) and src[s_idx] == "=":
                # 相等判断
                token = Token.EQ
                s_idx += 1
            else:
                # 赋值
                token = Token.ASSIGN
            return
        elif token == "+":
            if s_idx < len(src) and src[s_idx] == "+":
                # 自增
                token = Token.INC
                s_idx += 1
            else:
                # 加法
                token = Token.ADD
            return
        elif token == "-":
            if s_idx < len(src) and src[s_idx] == "-":
                # 自减
                token = Token.DEC
                s_idx += 1
            else:
                # 减法
                token = Token.SUB
            return
        elif token == "!" and s_idx < len(src) and src[s_idx] == "=":
            # 不等于
            token = Token.NE
            s_idx += 1
            return
        elif token == "<":
            if s_idx < len(src):
                if src[s_idx] == "=":
                    # 小于等于
                    token = Token.LE
                    s_idx += 1
                elif src[s_idx] == "<":
                    # 左移
                    token = Token.SHL
                    s_idx += 1
            else:
                # 小于
                token = Token.LT
            return
        elif token == ">":
            if s_idx < len(src):
                if src[s_idx] == "=":
                    # 大于等于
                    token = Token.GE
                    s_idx += 1
                elif src[s_idx] == ">":
                    # 右移
                    token = Token.SHR
                    s_idx += 1
            else:
                # 大于
                token = Token.GT
            return
        elif token == "|":
            if s_idx < len(src):
                if src[s_idx] == "|":
                    # 逻辑或
                    token = Token.LOR
                    s_idx += 1
            else:
                # 或
                token = Token.OR
            return
        elif token == "&":
            if s_idx < len(src):
                if src[s_idx] == "&":
                    # 逻辑与
                    token = Token.LAN
                    s_idx += 1
            else:
                # 与
                token = Token.AND
            return
        elif token == "^":
            # 异或
            token = Token.XOR
            return
        elif token == "%":
            # MOD
            token = Token.MOD
            return
        elif token == "*":
            # 乘法
            token = Token.MUL
            return
        elif token == "[":
            token = Token.BRAK
            return
        elif token == "?":
            # 三目运算符
            token = Token.COND
            return
        elif token == "~" or token == ";" or token == "{" or token == "}" or\
            token == "(" or token == ")" or token == "]" or token == "," or token == ":":
            return
        elif token == "#":
            # 宏定义全部跳过
            while s_idx < len(src) and src[s_idx] != "\n":
                s_idx += 1
            s_idx += 1
        elif token == " ":
            continue
        else:
            print("unknown: " + src[s_idx:], token)
            exit(0)

# 语法分析
def program():
    pass

# 表达式解析
def expression():
    pass

# 虚拟机入口
def eval():
    i = 0
    global memory, data, heap, bp, sp, pc, ax
    while True:
        op = memory[pc]
        pc += 1
        if Debug:
            print("##### {} #####".format(i + 1))
            print("op = {}, pc = {}, ax = {}".format(op, pc - 1, ax))
        if op == Inst.LEA:
            # 通过bp快速检索到变量的位置
            ax = bp + memory[pc]
            pc += 1
        elif op == Inst.IMM:
            ax = memory[pc]
            pc += 1
        elif op == Inst.JMP:
            pc = memory[pc]
        elif op == Inst.CALL:
            # 记录下来调用返回时执行的下一条指令
            sp -= 1
            memory[sp] = pc + 1
            # 方法跳转
            pc = memory[pc]
        elif op == Inst.JZ:
            pc = memory[pc] if ax == 0 else pc + 1
        elif op == Inst.JNZ:
            pc = memory[pc] if ax != 0 else pc + 1
        elif op == Inst.ENT:
            # 记录下来旧的bp
            sp -= 1
            memory[sp] = bp
            # 开辟出局部变量的空间
            bp = sp
            sp = sp - memory[pc]
            pc += 1
        elif op == Inst.ADJ:
            # 函数执行完成后，快速的把参数变量弹出栈
            sp = sp + memory[pc]
            pc += 1
        elif op == Inst.LEV:
            sp = bp
            bp = memory[sp]
            sp += 1
            pc = memory[sp]
            sp += 1
        elif op == Inst.LI or op == Inst.LC:
            ax = memory[ax]
        elif op == Inst.SI or op == Inst.SC:
            memory[memory[sp]] = ax
            sp += 1
        elif op == Inst.PUSH:
            sp -= 1
            memory[sp] = ax
        elif op == Inst.OR:
            ax = memory[sp] | ax
            sp += 1
        elif op == Inst.XOR:
            ax = memory[sp] ^ ax
            sp += 1
        elif op == Inst.AND:
            ax = memory[sp] & ax
            sp += 1
        elif op == Inst.EQ:
            ax = memory[sp] == ax
            sp += 1
        elif op == Inst.NE:
            ax = memory[sp] != ax
            sp += 1
        elif op == Inst.LT:
            ax = 1 if memory[sp] < ax else 0
            sp += 1
        elif op == Inst.GT:
            ax = 1 if memory[sp] > ax else 0
            sp += 1
        elif op == Inst.LE:
            ax = 1 if memory[sp] <= ax else 0
            sp += 1
        elif op == Inst.GE:
            ax = 1 if memory[sp] >= ax else 0
            sp += 1
        elif op == Inst.SHL:
            ax = memory[sp] << ax
            sp += 1
        elif op == Inst.SHR:
            ax = memory[sp] >> ax
            sp += 1
        elif op == Inst.ADD:
            ax = memory[sp] + ax
            sp += 1
        elif op == Inst.SUB:
            ax = memory[sp] - ax
            sp += 1
        elif op == Inst.MUL:
            ax = memory[sp] * ax
            sp += 1
        elif op == Inst.DIV:
            ax = memory[sp] / ax
            sp += 1
        elif op == Inst.MOD:
            ax = memory[sp] % ax
            sp += 1
        elif op == Inst.PRTF:
            # 注意：这里这么书写的原因是当执行PRTF的时候，当前帧的状态应该是
            #               pc
            # text = [PRTF, ADJ , 2]
            #          sp
            # stack = [100, "i = %d", "Other"]
            # 可以看到memory[pc + 1]取到的是参数数量2
            # temp指向栈中print方法的第一个参数的上一个位置
            temp = sp + memory[pc + 1]
            l = []
            for i in range(memory[pc + 1] - 1):
                l.append(memory[temp -2 - i])
            s = memory[temp - 1] % tuple(l)
            ax = len(s)
            print(s)
        elif op == Inst.EXIT:
            print("exit {}".format(memory[sp]))
            return memory[sp]
        else:
            # 不能识别的操作符
            print("unknown inst op = {}".format(op))
            return
        
        if Debug:
            print("data = {}".format(memory[data:data + 5]))
            print("stack = {}".format(memory[sp:]))
            print("heap = {}".format(memory[heap:heap + 25]))
            print("op = {}, pc = {}, ax = {}".format(op, pc, ax))
        i += 1

i_code = 0
def _code_reset():
    global i_code
    i_code = text
    for i in range(PoolSize):
        memory[text + i] = "#"      
def _code_append(op, v = None):
    global i_code
    memory[i_code] = op
    i_code += 1
    if v == None:
        return
    memory[i_code] = v
    i_code += 1
    
i_data = 0
def _data_reset():
    global i_data
    i_data = data
    for i in range(PoolSize):
        memory[data + i] = "#"
def _data_append(d):
    global i_data
    memory[i_data] = d
    i_data += 1

def main():
    # region 初始化内存
    global memory, text, data, heap, stack, bp, sp, pc, ax
    # 为了方便进行调试打印，对于未被使用的内存，使用"#"进行标记站位
    memory = ["#"] * 4 * PoolSize
    text = 0
    data = PoolSize
    heap = 2 * PoolSize
    stack = 4 * PoolSize
    bp = sp = 4 * PoolSize
    pc = ax = 0
    # endregion
    
    # region 虚拟机的测试代码
    # # 实现简单的 1 + 2的功能
    # _code_reset()
    # _code_append(Inst.IMM, 1)
    # _code_append(Inst.PUSH)
    # _code_append(Inst.IMM, 2)
    # _code_append(Inst.ADD)
    # _code_append(Inst.PUSH)
    # _code_append(Inst.EXIT)
    
    # # 实现简单的打印输出功能
    # # printf("i = %d, j = %d" % (100, 200))
    # _code_reset()
    # _code_append(Inst.IMM, "i = %d, j = %d")
    # _code_append(Inst.PUSH)
    # _code_append(Inst.IMM, 100)
    # _code_append(Inst.PUSH)
    # _code_append(Inst.IMM, 200)
    # _code_append(Inst.PUSH)
    # _code_append(Inst.PRTF)
    # _code_append(Inst.ADJ, 3)
    # _code_append(Inst.PUSH)
    # _code_append(Inst.EXIT)
    
    # # # 实现简单的if语句
    # # if(10 > 2){
    # #     printf("10 is max")
    # # }else{
    # #     printf("2 is max")
    # # }
    # _code_reset()
    # _code_append(Inst.IMM, 10)
    # _code_append(Inst.PUSH)
    # _code_append(Inst.IMM, 2)
    # _code_append(Inst.GT)
    # _code_append(Inst.JZ, 13)
    # _code_append(Inst.IMM, "10 is max")
    # _code_append(Inst.PUSH)
    # _code_append(Inst.JMP, 16)
    # _code_append(Inst.IMM, "2 is max")
    # _code_append(Inst.PUSH)
    # _code_append(Inst.PRTF)
    # _code_append(Inst.ADJ, 1)
    # _code_append(Inst.PUSH)
    # _code_append(Inst.EXIT)
    
    # # 实现简单的函数调用
    # # int add(int a, int b) {
    # #     int ret;
    # #     ret = a + b;
    # #     return ret;
    # # }
    # # int main () {
    # #     printf("1 + 2 = %d", add(1, 2));
    # #     return 0;
    # # }
    # _code_reset()
    # _code_append(Inst.IMM, "1 + 2 = %d")
    # _code_append(Inst.PUSH)
    # _code_append(Inst.IMM, 1)
    # _code_append(Inst.PUSH)
    # _code_append(Inst.IMM, 2)
    # _code_append(Inst.PUSH)
    # _code_append(Inst.CALL, 19)
    # _code_append(Inst.ADJ, 2)
    # _code_append(Inst.PUSH)
    # _code_append(Inst.PRTF)
    # _code_append(Inst.ADJ, 2)
    # _code_append(Inst.PUSH)
    # _code_append(Inst.EXIT)
    # _code_append(Inst.ENT, 1)
    # _code_append(Inst.LEA, -1)
    # _code_append(Inst.PUSH)
    # _code_append(Inst.LEA, 3)
    # _code_append(Inst.LI)
    # _code_append(Inst.PUSH)
    # _code_append(Inst.LEA, 2)
    # _code_append(Inst.LI)
    # _code_append(Inst.ADD)
    # _code_append(Inst.SI)
    # _code_append(Inst.LEV)
    # endregion

    # region 把关键字放入词法分析中进行一遍分析
    global src
    src = ("char else enum if int return sizeof while "
           "open read close printf malloc free memset memcmp exit "
           "void main")

    # 关键词keyword
    for x in range(Token.CHAR.value, Token.WHILE.value + 1):
        next()
        current_id["Token"] = x

    # 系统调用
    for x in range(Inst.OPEN.value, Inst.EXIT.value + 1):
        next()
        current_id["Class"] = Token.SYS
        current_id["Type"] = Type.INT
        current_id["Value"] = x
    # void和main
    next()
    current_id["Token"] = Token.CHAR
    next()
    main_id = current_id
    # endregion
    
    # 读取c语言代码，并进行词法解析
    # 读取文件的源码
    try:
        ipt = os.path.join(os.getcwd(), "hello.c")
        f = open(ipt, "r")
        src = f.readlines()
        src = "".join(src)
        global s_idx
        s_idx = 0
    except IOError:
        print("Error:没有找到或读取 %s 失败" % ipt)
        sys.exit(2)
    else:
        f.close()
    program()
    
    eval()
main()
    